import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: AliceMana
 * Date: 2023-01-02
 * Time: 0:53
 */

// https://leetcode.cn/problems/last-stone-weight/
public class Solution2 {
    public static int lastStoneWeight0(int[] stones) {
        List<Integer> list = new LinkedList<>();
        for (int stone : stones) {
            list.add(stone);
        }

        while (list.size() >= 2) {
            list.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            });

            int ret = Math.abs(list.remove(0)-list.remove(0));
            if (ret != 0) {
                list.add(ret);
            }
        }
        if (list.isEmpty()) {
            return 0;
        }
        return list.get(0);
    }
    public static int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        for (int stone : stones) {
            priorityQueue.add(stone);
        }

        while (priorityQueue.size() >= 2) {
            int a = priorityQueue.poll();
            int b = priorityQueue.poll();
            if (a > b) {
                priorityQueue.offer(a-b);
            }
        }
        return priorityQueue.size() == 1 ? priorityQueue.poll() : 0;
    }


    public static void main(String[] args) {
        int[] arr = {2,7,4,1,8,1};
        System.out.println(lastStoneWeight(arr));
    }
}
